Graph _ II
int i = 0;
edges is array of edges;
//method num(vertex) assign number of the vertex pass to it.
cycleDetectionDFS(v){
num(v) = i++;
for all vertices u adjacent to v
if(num(v) == 0){
add edge uv to edges
cycleDetection DFS(u);
}else{
return cycle Detected;
}
}
Minimum spanning tree is a tree in which the sum of the weight of its edges
is minimal
Kruskal's Algorithm
Graph must be connected undirected graph
E is number of edges;
V is number of vertices;
KruskalAlgorithm(Grapgh G){
tree = null;
edges = all the edges of graph sorted by weight;
for(i=1;i<=|E| and |tree| < |V|-1;i++){
if(ei from edges does not form a cycle with edges in tree){
add ei to tree;
}
}
}
In many situations, tasks have to be performed in sequence as the order of tasks matters, it matters which task should be performed first. The dependencies between tasks can be show using directed graph (digraph) without cycle.
int i = 0;
V is number of vertices;
TopologicalSort(digraph){
for i=1 to |V|
find a minimal vertex v, vertex with minimum indegree or indegree = 0;
num(v) = i++;
perform depth first search for vertex v until vertex without any out going edge is reached, store
vertices in stack;
pop that vertex from stack, check if other edges can be traversed from elements of stack, if not
pop them out.
}
An undirected graph is called connected if there is a path between any two vertices of the graph. A vertex removal of which splits a graph into subgraphs is called articulation point or cut vertex. A graph is called n-connected if there are at least n different paths any two vertices without any vertex in common between those paths
A network can be explained as a network of pipelines used to deliver water to one destination from a source. Many pipes of different diameters with may pumping stations will be used to deliver water from source to destination, pumping power of stations will be different.